/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/decode-ways
   @Language: C++
   @Datetime: 19-05-29 15:33
   */

// Method 1, DP, Time O(n), Space O(n), Time 6ms
class Solution {
public:
	/**
	 * @param s: a string,  encoded message
	 * @return: an integer, the number of ways decoding
	 */
	int numDecodings(string &s) {
		// write your code here
		if(s.length()==0 || s.find("00")!=s.npos) return 0;
		vector<int> dp(s.length()+1,0);
		dp[0]=1;
		for(int i=0; i<s.length(); ++i){
			if(s[i]>'0') dp[i+1]=dp[i];
			if(i>0){
				const int num=(s[i-1]-'0')*10+s[i]-'0';
				if(num>26 && s[i]=='0') return 0;
				if(num>9 && num<27) dp[i+1]+=dp[i-1];
			}
		}
		return dp.back();
	}
};

// Method 2, DP, Time O(n), Space O(1), Time 8ms
class Solution {
public:
	/**
	 * @param s: a string,  encoded message
	 * @return: an integer, the number of ways decoding
	 */
	int numDecodings(string &s) {
		// write your code here
		if(s.length()==0 || s.find("00")!=s.npos) return 0;
		int pp=0, p=0, cur=1;
		for(int i=0; i<s.length(); ++i){
			pp=p, p=cur, cur=0;
			if(s[i]>'0') cur=p;
			if(i>0){
				const int num=(s[i-1]-'0')*10+s[i]-'0';
				if(num>26 && s[i]=='0') return 0;
				if(num>9 && num<27) cur+=pp;
			}
		}
		return cur;
	}
};
